import { isNumber } from "lodash";
import { ListNode } from "../../const";

/**
 * @name 最长回文子串
 * @link https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function longestPalindrome(s: string): string {
  const len = s.length;
  if (len < 2) return s;

  // 记录最大长度
  let maxLen = 1;
  let begin = 0;

  let dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len);
  }
  console.log(dp);
  //   初始化所有长度为1的子串为回文串
  for (let i = 0; i < len; i++) {
    dp[i][i] = true;
  }

  for (let sLen = 2; sLen <= len; sLen++) {
    for (let i = 0; i < len; i++) {
      let j = sLen + i - 1;
      if (j >= len) break;

      if (s[i] !== s[j]) {
        dp[i][j] = false;
      } else {
        if (j - i < 3) {
          dp[i][j] = true;
        } else {
          dp[i][j] = dp[i + 1][j - 1];
        }
      }

      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        begin = i;
      }
    }
  }

  return s.slice(begin, begin + maxLen);
}

/**
 * Do not return anything, modify s in-place instead.
 * @name 反转字符串中的单词
 * @link https://leetcode.cn/problems/reverse-words-in-a-string-ii/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function reverseWords(s: string[]): void {
  let target = s.reverse().join("");
  let list = target.split(" ");
  let res = [];
  for (let i = 0; i < list.length; i++) {
    res.push(...list[i].split("").reverse());
    if (i !== list.length - 1) {
      res.push(" ");
    }
  }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  let hodd = head;
  let heven = head.next;
  let oddTmp = hodd;
  let evenTmp = heven;
  let tmp = head.next.next;
  let flag = false;
  while (tmp) {
    if (flag) {
      flag = false;
      evenTmp.next = tmp;
      evenTmp = evenTmp.next;
    } else {
      flag = true;
      oddTmp.next = tmp;
      oddTmp = oddTmp.next;
    }
    tmp = tmp.next;
  }
  oddTmp.next = heven;
  evenTmp.next = null;
  return hodd;
}

/**
 * @name 同构字符串
 * @link https://leetcode.cn/problems/isomorphic-strings/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function isIsomorphic(s: string, t: string): boolean {
  //   let len = s.length;
  //   let dict: { [key: string]: string } = {};
  //   let sDic: { [key: string]: number } = {};
  //   let tDic: { [key: string]: number } = {};
  //   if (len !== t.length) return false;
  //   for (let i = 0; i < len; i++) {
  //     if (dict.hasOwnProperty(s[i])) {
  //       // 如果存在映射且后续的和该映射不符返回false
  //       console.log(dict[s[i]], t[i]);

  //       if (dict[s[i]] !== t[i]) return false;
  //     } else {
  //       dict[s[i]] = t[i];
  //     }
  //     // s字符串字母出现字典表
  //     if (sDic.hasOwnProperty(s[i])) {
  //       sDic[s[i]] += 1;
  //     } else {
  //       sDic[s[i]] = 1;
  //     }
  //     // t字符串字母出现字典表
  //     if (tDic.hasOwnProperty(t[i])) {
  //       tDic[t[i]]++;
  //     } else {
  //       tDic[t[i]] = 1;
  //     }
  //   }

  //   if (Object.keys(sDic).length !== Object.keys(tDic).length) return false;
  //   for (let i = 0; i < len; i++) {
  //     if (!tDic.hasOwnProperty(dict[s[i]])) return false;
  //     tDic[dict[s[i]]] -= 1;
  //     if (tDic[dict[s[i]]] < 0) return false;
  //   }

  //   console.log(dict, tDic);

  //   return true;
  let s2t: { [key: string]: string } = {};
  let t2s: { [key: string]: string } = {};
  let len = s.length;
  for (let i = 0; i < len; i++) {
    const x = s[i],
      y = t[i];
    if ((s2t[x] && s2t[x] !== y) || (t2s[y] && t2s[y] !== x)) return false;
    s2t[x] = y;
    t2s[y] = x;
  }

  return true;
}

/**
 * @name 反转链表
 * @link https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let nodeList = [];
  let tmp = head as ListNode | null;
  while (tmp) {
    nodeList.push(tmp);
    tmp = tmp.next;
  }

  nodeList = nodeList.reverse();
  for (let i = 0; i < nodeList.length; i++) {
    if (i + 1 < nodeList.length) nodeList[i].next = nodeList[i + 1];
    else nodeList[i].next = null;
  }
  return nodeList[0];
}

/**
 * @name 三数之和
 * @link https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function threeSum(nums: number[]): number[][] {
  if (nums.length < 3) return [];
  nums = nums.sort((a, b) => a - b);
  console.log(nums);

  let res: number[][] = [];

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) break;
    if (i - 1 >= 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      if (nums[i] + nums[left] + nums[right] === 0) {
        if (
          left + 1 < right - 1 &&
          nums[left] === nums[left + 1] &&
          nums[right] === nums[right - 1]
        ) {
        } else {
          res.push([nums[i], nums[left], nums[right]]);
        }
        left++;
        right--;
      } else if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  console.log(res);

  return res;
}

/**
 * @name 两数之和
 * @link https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function twoSum(nums: number[], target: number): number[] {
  // 暴力枚举
  //   let len = nums.length;
  //   for (let i = 0; i < len; i++) {
  //     for (let j = i + 1; j < len; j++) {
  //       if (nums[i] + nums[j] === target) {
  //         return [i, j];
  //       }
  //     }
  //   }
  //   return [];
  // 哈希表方法复杂度更低
  let dic: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    let tmp = dic.indexOf(nums[i]);
    if (tmp > -1) {
      return [tmp, i];
    }
    dic.push(target - nums[i]);
  }
  return [];
}

/**
 * @name 打家劫舍
 * @link https://leetcode.cn/problems/house-robber-ii/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function rob(nums: number[]): number {
  if (nums.length < 2) return nums?.length ? nums[0] : 0;
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  let ans = 0;
  let dp: number[] = [];
  // 选起始点
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length - 1; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  ans = dp[dp.length - 1];
  // 不选起始点
  dp = [];
  dp[1] = nums[1];
  dp[2] = Math.max(nums[1], nums[2]);
  for (let i = 3; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  ans = Math.max(ans, dp[dp.length - 1]);
  return ans;
}

/**
 * @name 简化路径
 * @link https://leetcode.cn/problems/simplify-path/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function simplifyPath(path: string): string {
  // 存放路径
  let stack = [];
  let begin = 0;
  let filename = "";
  for (let i = 0; i < path.length; i++) {
    if (path[i] === "/" && path[i + 1] === "/") continue;
    if (path[i] === "/" && begin === 0) {
      begin = 1;
      continue;
    }
    if (path[i] === "/" && begin === 1) {
      if (filename !== "") {
        if (filename === "..") {
          stack.pop();
          filename = "";
          continue;
        }
        if (filename === ".") {
          filename = "";
          continue;
        }
        stack.push(filename);
      }
      filename = "";
      continue;
    }
    filename += path[i];
  }
  if (filename !== "") {
    if (filename === "..") {
      stack.pop();
      filename = "";
    } else if (filename === ".") {
      filename = "";
    } else stack.push(filename);
  }
  console.log(stack);

  let ans = "";
  stack.map((ss) => (ans += "/" + ss));

  return ans === "" ? "/" : ans;
}

/**
 * @name 串联字符串的最大长度
 * @link https://leetcode.cn/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function maxLength(arr: string[]): number {
  let ans = 0;
  const masks = [];
  for (const s of arr) {
    let mask = 0;
    for (let i = 0; i < s.length; i++) {
      const ch = s[i].charCodeAt(0) - "a".charCodeAt(0);
      if (((mask >> ch) & 1) !== 0) {
        // 含有重复字符
        mask = 0;
        break;
      }
      mask = mask | (1 << ch);
    }
    if (mask > 0) {
      masks.push(mask);
    }
  }
  // console.log(masks.map((m) => m.toString(2)));
  // 回溯
  const backtrack = (masks: number[], pos: number, mask: number) => {
    if (pos === masks.length) {
      ans = Math.max(ans, mask.toString(2).split("0").join("").length);
      return;
    }
    if ((mask & masks[pos]) === 0) {
      backtrack(masks, pos + 1, mask | masks[pos]);
    }
    backtrack(masks, pos + 1, mask);
  };
  backtrack(masks, 0, 0);
  return ans;
}

/**
 * @name 螺旋矩阵
 * @link https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function spiralOrder(matrix: number[][]): number[] {
  if (matrix.length < 1) {
    return [];
  }
  let ans = [];
  let boundary = [matrix[0].length, matrix.length, -1, 0];
  let count = matrix[0].length * matrix.length;
  let i = 0,
    j = 0;
  let dir = 0;
  while (count) {
    console.log(i, j, dir);

    ans.push(matrix[i][j]);
    count--;
    if (dir === 0) {
      // right
      j++;
      if (j === boundary[dir]) {
        console.log("over right");
        // 超过最右侧
        boundary[dir] -= 1;
        dir += 1;
        j--;
        i++;
      }
      continue;
    }
    if (dir === 1) {
      // bottom
      i++;
      if (i === boundary[dir]) {
        console.log("over bottom");
        // 超过最下侧
        boundary[dir] -= 1;
        dir += 1;
        i--;
        j--;
      }
      continue;
    }
    if (dir === 2) {
      // left
      j--;
      if (j === boundary[dir]) {
        console.log("over left");
        // 超过最左侧
        boundary[dir] += 1;
        dir += 1;
        j++;
        i--;
      }
      continue;
    }
    if (dir === 3) {
      // top
      i--;
      if (i === boundary[dir]) {
        console.log("over top");
        // 超过最上侧
        boundary[dir] += 1;
        dir = dir + 1 > 3 ? 0 : dir + 1;
        i++;
        j++;
      }
      continue;
    }
  }
  console.log(ans);

  return ans;
}

/**
 * @name 最长公共子序列
 * @link https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function longestCommonSubsequence(text1: string, text2: string): number {
  let m = text1.length;
  let n = text2.length;
  if (!m || !n) return 0;
  const dp = new Array(m + 1);
  for (let i = 0; i < m + 1; i++) {
    dp[i] = new Array(n + 1);
  }

  console.log(dp);

  // 动态规划边界条件
  for (let i = 0; i < m + 1; i++) {
    dp[i][0] = 0;
  }
  for (let i = 0; i < n + 1; i++) {
    dp[0][i] = 0;
  }

  for (let i = 1; i < m + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      // 相等
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      // 不等
      else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  console.log(dp);

  return dp[m][n];
}

/**
 * @name 字符串相加
 * @link https://leetcode.cn/problems/add-strings/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function addStrings(num1: string, num2: string): string {
  let cmp = 0;
  let unit = 1;
  let ans = "";
  let len = Math.min(num1.length, num2.length);
  for (let i = 0; i < len; i++) {
    if (
      Number(num1[num1.length - unit]) +
        Number(num2[num2.length - unit]) +
        cmp <
      10
    ) {
      ans +=
        Number(num1[num1.length - unit]) +
        Number(num2[num2.length - unit]) +
        cmp;
      cmp = 0;
    } else {
      ans +=
        Number(num1[num1.length - unit]) +
        Number(num2[num2.length - unit]) +
        cmp -
        10;
      cmp = 1;
    }
    unit += 1;
  }
  console.log(ans, unit, num1, num2, cmp);

  while (unit <= num1.length) {
    if (Number(num1[num1.length - unit]) + cmp < 10) {
      ans += Number(num1[num1.length - unit]) + cmp;
      cmp = 0;
    } else {
      console.log(Number(num1[num1.length - unit]) + cmp - 10);
      ans += Number(num1[num1.length - unit]) + cmp - 10;
      cmp = 1;
    }
    unit += 1;
  }
  while (unit <= num2.length) {
    if (Number(num2[num2.length - unit]) + cmp < 10) {
      ans += Number(num2[num2.length - unit]) + cmp;
      cmp = 0;
    } else {
      console.log(Number(num2[num2.length - unit]) - 10);

      ans += Number(num2[num2.length - unit]) + cmp - 10;
      cmp = 1;
    }
    unit += 1;
  }
  if (cmp === 1) {
    ans += "1";
  }

  console.log(ans);

  return ans.split("").reverse().join("");
}

/**
 * @name 笨阶乘
 * @link https://leetcode.cn/problems/clumsy-factorial/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function clumsy(n: number): number {
  let stack: number[] = [];
  // 正负
  let flag = 1;
  let ans = 0;
  for (let i = n; i > 0; i--) {
    if (stack.length === 4) {
      let tmp = flag * Math.floor((stack[0] * stack[1]) / stack[2]) + stack[3];
      console.log(tmp, flag);
      ans += tmp;
      flag = -1;
      stack = [];
    }
    stack.push(i);
  }
  console.log(ans, stack, flag);

  if (stack.length === 1) {
    ans += flag * stack[0];
  }
  if (stack.length === 2) {
    ans += flag * stack[0] * stack[1];
  }
  if (stack.length === 3) {
    ans += flag * Math.floor((stack[0] * stack[1]) / stack[2]);
  }
  if (stack.length === 4) {
    let tmp = flag * Math.floor((stack[0] * stack[1]) / stack[2]) + stack[3];
    ans += tmp;
  }
  console.log(ans);

  return ans;
}

/**
 * @name 受标签影响的最大值
 * @link https://leetcode.cn/problems/largest-values-from-labels/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function largestValsFromLabels(
  values: number[],
  labels: number[],
  numWanted: number,
  useLimit: number
): number {
  let len = values.length;
  let indexes = new Array(len);
  for (let i = 0; i < indexes.length; i++) {
    indexes[i] = i;
  }

  // 根据value数组对indexes进行排序

  let ans = 0;
  let count = 0;
  let dict: { [key: number]: number } = {};
  for (let i = 0; i < indexes.length; i++) {
    // 判断到足够个数则跳出循环
    if (count === numWanted) break;
    if (dict.hasOwnProperty(labels[indexes[i]])) {
      if (dict[labels[indexes[i]]] >= useLimit) {
        continue;
      } else {
        ans += values[indexes[i]];
        // console.log("add: ", values[indexes[i]]);
        dict[labels[indexes[i]]] += 1;
        count++;
      }
    } else {
      ans += values[indexes[i]];
      // console.log("add: ", values[indexes[i]]);
      dict[labels[indexes[i]]] = 1;
      count++;
    }
  }
  return ans;
}

/**
 * @name 两数相加
 * @link https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let head: ListNode | null = null;
  let tmp = null;

  let tmp1 = l1;
  let tmp2 = l2;
  let cmp = 0;
  while (tmp1 || tmp2) {
    let num = cmp + (tmp1 ? tmp1?.val : 0) + (tmp2 ? tmp2?.val : 0);
    console.log(num);
    if (num >= 10) {
      cmp = 1;
      num = num - 10;
    } else {
      cmp = 0;
    }
    if (!tmp) {
      tmp = new ListNode(num);
      head = tmp;
    } else {
      tmp.next = new ListNode(num);
      tmp = tmp.next;
    }

    if (tmp1) tmp1 = tmp1.next;
    if (tmp2) tmp2 = tmp2.next;
  }

  if (cmp && tmp) {
    tmp.next = new ListNode(cmp);
  }
  return head;
}

/**
 * @name 最大间距
 * @link https://leetcode.cn/problems/maximum-gap/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function maximumGap(nums: number[]): number {
  // 基数排序
  const n = nums.length;
  if (n < 2) {
    return 0;
  }
  let exp = 1;
  const buf = new Array(n).fill(0);
  const maxVal = Math.max(...nums);

  while (maxVal >= exp) {
    const cnt = new Array(10).fill(0);
    for (let i = 0; i < n; i++) {
      let digit = Math.floor(nums[i] / exp) % 10;
      cnt[digit]++;
    }
    for (let i = 1; i < 10; i++) {
      cnt[i] += cnt[i - 1];
    }
    for (let i = n - 1; i >= 0; i--) {
      let digit = Math.floor(nums[i] / exp) % 10;
      buf[cnt[digit] - 1] = nums[i];
      cnt[digit]--;
    }
    nums.splice(0, n, ...buf);
    exp *= 10;
  }

  let ret = 0;
  for (let i = 1; i < n; i++) {
    ret = Math.max(ret, nums[i] - nums[i - 1]);
  }

  console.log(ret);

  return ret;
}

/**
 * @name 组合总和
 * @link https://leetcode.cn/problems/combination-sum/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function combinationSum(candidates: number[], target: number): number[][] {
  candidates = candidates.sort((a, b) => b - a);
  let ans: number[][] = [];
  const backtrack = (pos: number, stack: number[], tmp: number) => {
    // console.log(pos, stack, tmp, candidates[pos]);

    if (tmp > target) {
      return;
    }
    if (tmp === target) {
      ans.push([...stack]);
      return;
    }
    stack.push(candidates[pos]);
    tmp += candidates[pos];

    backtrack(pos, stack, tmp);

    tmp -= stack[stack.length - 1];
    stack.pop();
    if (pos + 1 < candidates.length) backtrack(pos + 1, stack, tmp);
  };

  backtrack(0, [], 0);
  return ans;
}

/**
 * @name 394.字符串解码
 * @link https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function decodeString(s: string): string {
  // 3[a2[c]]
  let ans = "";
  let stack = [];
  let end = 0;
  while (end < s.length) {
    let tmp = "";
    // 将整数拼接
    while (!isNaN(Number(s[end]))) {
      tmp += s[end];
      end++;
    }
    if (tmp !== "") {
      stack.push(tmp);
      tmp = "";
    }
    if (s[end] === "]") {
      let prev = "";
      let top = stack[stack.length - 1];
      while (top !== "[") {
        if (!isNaN(Number(top))) {
          let ttmp = "";
          for (let i = 0; i < Number(top) - 1; i++) {
            ttmp += prev;
          }
          tmp += ttmp;
        } else {
          tmp += top;
          prev = top;
        }
        stack.pop();
        top = stack[stack.length - 1];
      }
      stack.pop();
      stack.push(tmp);
      end++;
      console.log(stack);
    } else {
      stack.push(s[end]);
      end++;
    }
  }
  // console.log(stack);

  let tmp = "";
  while (stack.length) {
    let top = stack[stack.length - 1];
    if (!isNaN(Number(top))) {
      let ttmp = "";
      for (let i = 0; i < Number(top) - 1; i++) {
        ttmp += tmp;
      }
      ans += ttmp;
      tmp = "";
    } else {
      tmp = top;
      ans += top;
    }
    stack.pop();
  }
  console.log(ans);

  return ans.split("").reverse().join("");
}

/**
 * @name 19.删除链表的倒数第n个节点
 * @link https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=huawei-2023-fall-sprint
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (!head) return null;
  const list = [];
  let tmp: ListNode | null = head;
  while (tmp) {
    list.push(tmp);
    tmp = tmp.next;
  }
  if (list.length - n - 1 >= 0 && list.length - n + 1 < list.length)
    list[list.length - n - 1].next = list[list.length - n + 1];
  if (list.length - n - 1 >= 0 && list.length - n + 1 >= list.length) {
    list[list.length - n - 1].next = null;
  }
  if (list.length - n - 1 < 0) {
    head = head.next;
  }

  return head;
}

export default {
  longestPalindrome,
  reverseWords,
  oddEvenList,
  isIsomorphic,
  reverseList,
  threeSum,
  rob,
  simplifyPath,
  twoSum,
  maxLength,
  spiralOrder,
  longestCommonSubsequence,
  addStrings,
  clumsy,
  largestValsFromLabels,
  addTwoNumbers,
  combinationSum,
  decodeString,
};
